package javalearn;
import java.util.*;
import java.util.stream.StreamSupport;

public class ToolClass {
    /**
     * 两数之和求数组序列
     *
     * @param nums   数组
     * @param target 目标值
     * @return 两数之和为目标值的数组索引
     */
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }

    /**
     * 有序数组插入位置
     *
     * @param nums   数组
     * @param target 插入值
     * @return 插入值数组索引位置
     */
    public static int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return 0;
    }

    /**
     * 求两个有序数组的中位数
     *
     * @param nums1 有序数组1
     * @param nums2 有序数组2
     * @return 中位数
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total = nums1.length + nums2.length;
        double[] merged = new double[total];
        int i = 0, j = 0;
        for (int k = 0; k < merged.length; k++) {
            if (i < nums1.length && j < nums2.length) {
                if (nums1[i] > nums2[j]) {
                    merged[k] = nums2[j];
                    j++;
                } else {
                    merged[k] = nums1[i];
                    i++;
                }
            } else {
                if (i >= nums1.length) {
                    merged[k] = nums2[j];
                    j++;
                } else {
                    merged[k] = nums1[i];
                    i++;
                }

            }

        }
        System.out.println(Arrays.toString(merged));
        if (merged.length % 2 == 0) {
            return (merged[total / 2] + merged[total / 2 - 1]) / 2;
        } else {
            return merged[total / 2];
        }
    }

    /**
     * 三数之和为0，返回所有的三数组合可能
     *
     * @param nums 数组
     * @return 三数组合数组
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int target = -nums[i];
            int k = nums.length - 1;
            for (int j = i + 1; j < nums.length; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                while (j < k && nums[j] + nums[k] > target) {
                    k--;
                }
                if (j == k) {
                    break;
                }
                if (nums[j] + nums[k] == target) {
                    List<Integer> result = Arrays.asList(nums[i], nums[j], nums[k]);
                    results.add(result);
                }
            }
        }
        return results;
    }

    public static int romanToInt(String s) {
        Map<Character, Integer> hashtable = new HashMap<>();
        hashtable.put('I', 1);
        hashtable.put('V', 5);
        hashtable.put('X', 10);
        hashtable.put('L', 50);
        hashtable.put('C', 100);
        hashtable.put('D', 500);
        hashtable.put('M', 1000);
        int sum = 0;
        int before = 0;
        for (int i = 0; i < s.length(); i++) {
            sum += hashtable.get(s.charAt(i));
            if (hashtable.get(s.charAt(i)) > before) {
                sum = sum - 2 * before;
            }

            before = hashtable.get(s.charAt(i));
        }
        return sum;
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String predix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            predix = longestCommonPrefix(predix, strs[i]);
            if (predix.length() == 0) {
                break;
            }
        }
        return predix;
    }

    public static String longestCommonPrefix(String str1, String str2) {
        int count = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < count && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }

    public static boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }
        Stack<Character> st = new Stack<>();
        Map<Character, Character> hashtable = new HashMap<>();
        hashtable.put('(', ')');
        hashtable.put('[', ']');
        hashtable.put('{', '}');
        for (int i = 1; i < s.length(); i++) {
            if(s.charAt(i)=='{'||s.charAt(i)=='['||s.charAt(i)=='('){
                st.push(s.charAt(i));
            }else{
                if (st.empty()) return false;
                if(s.charAt(i) == hashtable.get(st.peek())){
                    st.pop();
                }else return false;
            }

        }
        return st.isEmpty();
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null)return list2;
        if(list2==null)return list1;
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while (list1!=null&&list2!=null){
            if(list1.val<list2.val){
                cur.next = list1;
                list1 = list1.next;
            }else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if(list1==null){
            cur.next = list2;
        }else {
            cur.next = list1;
        }
        return head.next;

    }
}
class ListNode {
      int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }